package com.dong.algorithm.novice.linkedlist;

/**
 * 经典题目：用双链表结构实现双端队列
 * 每个操作都是时间复杂度O(1)
 *
 * @author by jiweidong on 2021/12/6.
 */
public class Arg03_DoubleLinkedListToDeque {

    private static class Node<T> {
        private T value;
        private Node<T> next;
        private Node<T> last;

        public Node(T data) {
            this.value = data;
            this.next = null;
            this.last = null;
        }
    }

    public static class MyDeque<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyDeque (){
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

        public boolean isEmpty() {
            return this.size == 0;
        }

        public int size() {
            return this.size;
        }

        public void pushHead(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }

        public void pushTail(V value) {
            Node<V> cur = new Node<>(value);
            if (tail == null) {
                tail = cur;
                head = cur;
            } else {
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
            size++;
        }

        public V popHead(){
            V ans = null;
            if (head == null) {
                return ans;
            }
            ans = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            size--;
            return ans;
        }

        public V popTail(){
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            return ans;
        }

        public V peekHead(){
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }

        public V peekTail(){
            V ans = null;
            if (tail != null) {
                ans = tail.value;
            }
            return ans;
        }

    }


}
